package hyy_2022;


import commons.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 回文链表
 */
public class _0728_234_PalindromeList {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        System.out.println(isPalindrome(node1));

    }


    /**
     * 胡瑶瑶解题思路来一波:
     * 1、计算链表的长度n,如果为0,则不是回文链表,如果为1,则为回文链表
     * 2、遍历前半部分链表,用栈保存n/2个节点(利用栈先进后出的特点)
     * 3、遍历后半部分链表,将遍历节点值与栈顶元素作比较,如不相等,则不为回文链表,如相等，则继续遍历链表,直至链表最后一个节点
     * 4、注意点:如果链表个数为奇数,遍历后半部分链表时,需跳过最中间元素
     * @param head
     * @return boolean
     */
    public static boolean isPalindrome(ListNode head) {
        //计算链表节点个数
        int nodeNum = 0;
        ListNode copy = head;
        while(copy != null) {
            nodeNum ++;
            copy = copy.next;
        }

        //根据链表节点个数做不同操作
        if(nodeNum == 0) {
            return false;
        } else if(nodeNum == 1) {
            return true;
        } else {
            int halfway = nodeNum / 2 ;
            int i = 0;
            Deque<ListNode> stack = new LinkedList<>();
            //加入链表中一半元素
            while(head != null) {
                stack.push(head);
                i ++;
                head = head.next;
                if(i == halfway) {
                    //加入一半元素后,如果链表节点元素为奇数,则head指向下一个元素
                    if(nodeNum % 2 != 0) {
                        head = head.next;
                    }
                    break;
                }
            }
            //加入一半元素后,遍历剩余元素,并且弹出栈顶元素与之比较
            while(head != null) {
                ListNode pop = stack.pop();
                if(pop.val != head.val) {
                    return false;
                } else {
                    head = head.next;
                }
            }
            return true;
        }
    }

}

